package com.wt.快速排序;

public class speediness {
    public void qsort(int array[]) {
        if (array.length > 1) {
            _qsort(array, 0, array.length - 1);
        }
    }

    /**
     * 一趟快速排序
     *
     * @param array
     */
    private void _qsort(int[] array, int low, int high) {
        if (low < high) {
            int middle = getMiddle(array, low, high);
            _qsort(array, low, middle - 1);
            _qsort(array, middle + 1, high);
        }
    }

    /**
     * 得到中间值
     */
    private int getMiddle(int[] array, int low, int high) {
        int tmp = array[low];
        while (low < high) {
            while (low < high && array[high] >= tmp) {
                high--;
            }
            array[low] = array[high];
            while (low < high && array[low] <= tmp) {
                low++;
            }
            array[high] = array[low];
        }
        array[low] = tmp;
        return low;
    }

    public static void main(String[] args) {
        int[] arr = {1, 7, 5, 6, 4, 2, 8, 9, 3, 10, 13, 12};
        speediness speediness = new speediness();
        speediness.qsort(arr);
        System.out.println("快速排序:");
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i]+"：");
        }

    }
}
